package com.wwz.leetcode;

import org.junit.Test;

import java.util.Deque;
import java.util.LinkedList;

public class LeetCode32 {
    // 我们始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」，这样的做法主要是考虑了边界条件的处理，栈里其他元素维护左括号的下标：
    //对于遇到的每个 ‘(’,我们将它的下标放入栈中
    //对于遇到的每个 ‘)’,我们先弹出栈顶元素表示匹配了当前右括号：
    //如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
    //如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」
    public int longestValidParentheses(String s) {
        int maxans = 0;
        // 双端队列
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            // 从头部压入元素
            if (s.charAt(i) == '(') {
                // 对于遇到的每个'(',我们将它的下标放入栈中
                stack.push(i);
            } else {
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;
    }

    @Test
    public void test() {
        // 预期6
//        System.out.println(longestValidParentheses("()(())"));
        // 预期2
          System.out.println(longestValidParentheses("()(()"));

    }
}
